//#include <iostream>
//#include <ctime>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];
//int get_random(int left, int right)
//{
//	return a[rand() % (right - left + 1) + left];
//}
//void quick_sort(int left, int right)
//{
//	if (left >= right)return;
//	int p = get_random(left, right);
//	int l = left - 1;int i = left;int r = right + 1;
//	while (i < r)
//	{
//		if (a[i] < p)
//		{
//			swap(a[++l], a[i++]);
//		}
//		else if (a[i] == p)i++;
//		else 
//		{
//			swap(a[i], a[--r]);
//		}
//		
//		
//	}//[left,l][l+1,r][r+1,right]
//	quick_sort(left, l);
//	quick_sort(r, right);
//}
//int main()
//{
//	srand(time(0));
//	int n;cin >> n;
//	for (int i = 1;i <= n;i++)
//		cin >> a[i];
//	quick_sort(1, n);
//	for (int i = 1;i <= n;i++)
//		cout << a[i] <<" ";
//	return 0;
//}